package lec19graph.part2mst;

import java.util.Arrays;


public class PrimTree {

    private static int INF = Integer.MAX_VALUE;

    private static void Prim(int[][] g, int start) {
        int n = g[0].length;
        int[] lowCost = new int[n];//保存顶点之间边的权值
        int min, k = 0;
        int[] adjVex = new int[n];//用于保存顶点下标
        //对两个数组的0号下标进行初始化，假设从A顶点开始，lowcost[0]=0，表示A已加入生成树，可以这样理解，lowcost中的某个数一旦被置为0，
        // 说明这个下标所在顶点表中的顶点被纳入生成树了，另外，adjvex[0]=0的含义是假设从A开始。
        //表示对lowcost和adjvex数组赋值，lowcost所赋的值是与A有关的边的权值，adjvex所赋的值全部是0。
        for (int i = 0; i < n; i++) {
            lowCost[i] = g[start][i];
            adjVex[i] = start;
        }

        for (int i = 1; i < n; i++) {
            System.err.println("lowCost=" + Arrays.toString(lowCost));
            System.err.println("adjVex=" + Arrays.toString(adjVex));
            min = INF;
            for (int j = 0; j < n; j++) {//lowcost[k]=0，表示顶点k已加入生成树，对于locost中0的值，以后都不进行操作。 从未选择的集合中选择一个最小边
                if (lowCost[j] != 0 && lowCost[j] < min) {
                    min = lowCost[j];
                    k = j;
                }
            }
            System.out.println(adjVex[k] + " " + k + " " + min);
            //Prim 算法核心 ：更新lowCost数组
            lowCost[k] = 0;//顶点 k已经加入了集合
            for (int j = 1; j < n; j++) {
                if (g[k][j] != 0 && g[k][j] < lowCost[j]) {
                    lowCost[j] = g[k][j];
                    adjVex[j] = k;
                }
            }
        }
        System.err.println("lowCost=" + Arrays.toString(lowCost));
        System.err.println("adjVex=" + Arrays.toString(adjVex));
    }

    public static void main(String[] args) {

        int[][] G = {
                {0, 1, 2, INF, INF, INF},
                {1, 0, 6, 11, INF, INF},
                {2, 6, 0, 9, 13, INF},
                {INF, 11, 9, 0, 7, 3},
                {INF, INF, 13, 7, 0, 4},
                {INF, INF, INF, 3, 4, 0}};
        Prim(G, 0);

    }
}
